package offer;

import sun.awt.image.ImageWatched;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author Elephas
 * @Date 2022/2/6
 **/
@FunctionalInterface
public interface FindMinHeightTrees {
    /**
     * A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.
     *
     * Given a tree of n nodes labelled from 0 to n - 1,
     * and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree,
     * you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees,
     * those with minimum height (i.e. min(h))  are called minimum height trees (MHTs).
     *
     * Return a list of all MHTs' root labels.You can return the answer in any order.
     *
     * The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
     *
     * @param n
     * @param edges
     * @return
     */
    List<Integer> findMinHeightTrees(int n, int[][] edges);
}

class FindMinHeightTreesImpl1 implements FindMinHeightTrees{
    static final int[][] TEST_01_EDGES = new int[][]{{1,0},{1,2},{1,3}};
    static final int TEST_01_N = 4;

    public static void main(String[] args) {
        new FindMinHeightTreesImpl1().findMinHeightTrees(TEST_01_N, TEST_01_EDGES);
    }
    /**
     * DFS
     * @param n
     * @param edges
     * @return
     */
    static final int HAS_PATH = 1;
    static final int NO_PATH = 0;
    private int[][] matrixGraph;
    private int n;
    private int[][] edges;

    /**
     * o(n^3), o(n^2)
     * 超时，无法解决 n > 800 的情况
     * 解法一： 对每个点进行DFS，得到该节点位根节点的生成树的高度，每次DFS需要o(n^2）的时间
     * @param n
     * @param edges
     * @return
     */
    @Override
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if(n > 800){
            return null;
        }
        this.n = n;
        this.edges = edges;
        initMatrixGraph();
        int[] heights = new int[n];
        int minHeight = bfs(0);
        heights[0] = minHeight;
        for (int i = 1; i < n; i++) {
            heights[i] = bfs(i);
            if(heights[i] < minHeight){
                minHeight = heights[i];
            }
        }
        List<Integer> ans = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if(heights[i] == minHeight){
                ans.add(i);
            }
        }
        return ans;
    }
    private void initMatrixGraph(){
        this.matrixGraph = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrixGraph[i][j] = NO_PATH;
            }
        }
        for(int[] edge : edges){
            int i = edge[0];
            int j = edge[1];
            matrixGraph[i][j] = HAS_PATH;
            matrixGraph[j][i] = HAS_PATH;
        }
    }
    private int getPath(int i,int j){
        if(matrixGraph[i][j] == HAS_PATH){
            return HAS_PATH;
        }else{
            return NO_PATH;
        }
    }
    private int bfs(int vertex){
        int height = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(vertex);
        boolean[] isVisited = new boolean[n];
        for (int i = 0; i < n; i++) {
            isVisited[i] = false;
        }

        while(!queue.isEmpty()){
            int curQueueSize = queue.size();
            for (int i = 0; i < curQueueSize; i++) {
                int curVertex = queue.poll();
                isVisited[curVertex] = true;
                for (int j = 0; j < n; j++) {
                    if(getPath(curVertex,j) == HAS_PATH && !isVisited[j]){
                        queue.add(j);
                    }
                }
            }
            height++;
        }
        return height;
    }

}
class FindMinHeightTreesImpl2 implements FindMinHeightTrees{
    /**
     * 逆拓扑排序
     * @param n
     * @param edges
     * @return
     */
    @Override
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if(n == 1){
            List<Integer> ans = new ArrayList();
            ans.add(0);
            return ans;
        }
        int[] outDegrees = new int[n];

        // 用一个二维List来表示一个邻接表
        List<List<Integer>> map = new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            map.add(new ArrayList<>());
        }

        for(int[] edge : edges){
            int edgeHead = edge[0];
            int edgeTail = edge[1];
            outDegrees[edgeHead]++;
            outDegrees[edgeTail]++;
            map.get(edgeHead).add(edgeTail);
            map.get(edgeTail).add(edgeHead);
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if(outDegrees[i] == 1){
                queue.offer(i);
            }
        }
        boolean[] isVisited = new boolean[n];
        for (int i = 0; i < isVisited.length; i++) {
            isVisited[i] = false;
        }
        while(!queue.isEmpty()){
            ans = new ArrayList<>();
            int curQueueSize = queue.size();
            for (int i = 0; i < curQueueSize; i++) {
                int curVertex = queue.poll();
                ans.add(curVertex);
                List<Integer> neighbors = map.get(curVertex);
                for(int neighbor : neighbors){
                    outDegrees[neighbor]--;
                    if(outDegrees[neighbor] == 1){
                        queue.add(neighbor);
                    }
                }
            }
        }
        return ans;
    }
}